package com.yulongtian.weekCompetition.month202302.week02;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 参考 可
 * 先总结 再找答案
 * 预处理所有二进制结果
 * @author yulongTian
 * @create 2023-02-12 11:42
 */
public class Test03 {
    public static void main(String[] args) {
        String s = "101101";
//        int[][] queries = {{4, 2}, {3, 3}, {6, 4}, {9, 9}, {10, 28}, {0, 470}, {5, 83}, {10, 28}, {8, 15}, {6, 464}, {0, 3}, {5, 8}, {7, 7}, {8, 8}, {6, 208}, {9, 15}, {2, 2}, {9, 95}};
//        int[][] queries = {{0, 0}, {1, 1}, {2, 2}, {0, 1}};
        int[][] queries = {{0, 5}, {1, 2}};
        System.out.println(Arrays.deepToString(substringXorQueries(s, queries)));
    }


    /**
     * val ^ firsti == secondi
     * 转化为
     * val=secondi ^ firsti
     * 0~2**30-1
     * 预处理 s 的所有长度不超过 30 的子串
     * 用哈希表记录每个二进制数对应 的 left 和 right
     *
     * @param s
     * @param queries
     * @return
     */
    public static int[][] substringXorQueries(String s, int[][] queries) {
        int n = s.length();
        //<数,该数对应的最小的长度>
        HashMap<Integer, int[]> map = new HashMap<>();
        for (int left = 0; left < n; left++) {
            int x = 0;
            for (int right = left; right < Math.min(left + 30, n); right++) {
                x = (x << 1) | s.charAt(right) - '0';
                //map不存在x 或者当前的长度比之前存的长度小
                if (!map.containsKey(x) || right - left < map.get(x)[1] - map.get(x)[0]) {
                    map.put(x, new int[]{left, right});
                }
            }
        }
        int[][] ans = new int[queries.length][2];
        int[] temp = {-1, -1};
        for (int i = 0; i < queries.length; i++) {
            int x = queries[i][0];
            int y = queries[i][1];
            ans[i] = map.getOrDefault(x ^ y, temp);
        }
        return ans;
    }


//    //双指针法失败  54 / 59 个通过测试用例
//    public static int[][] substringXorQueries(String s, int[][] queries) {
//        List<int[]> temp = new ArrayList<>();
//
//        for (int[] query : queries) {
//            int target = query[0] ^ query[1];
//            if (target == 0) {
//                int index = 0;
//                while (s.charAt(index) != '0') {
//                    index++;
//                }
//                temp.add(new int[]{index, index});
//                continue;
//            }
//            int left = 0;
//            for (int right = 0; right < s.length(); right++) {
//                while (left <= right && s.charAt(left) == '0') {
//                    left++;
//                }
//                String s1 = s.substring(left, right + 1);
//                if (s1.equals("")) {
//                    if (right == s.length() - 1) {
//                        temp.add(new int[]{-1, -1});
//                    }
//                    continue;
//                }
//                int a = Integer.valueOf(s1, 2);
//                if (a == target) {
//                    temp.add(new int[]{left, right});
//                    right = s.length() + 2;
//                    break;
//                }
//                while (a > target) {
//                    while (true) {
//                        left++;
//                        if (left >= right || s.charAt(left) != '0') {
//                            break;
//                        }
//                    }
//                    s1 = s.substring(left, right + 1);
//                    if (s1.equals("")) {
//                        break;
//                    }
//                    a = Integer.valueOf(s1, 2);
//                    if (a == target) {
//                        temp.add(new int[]{left, right});
//                        right = s.length() + 2;
//                        break;
//                    }
//                }
//                if (right == s.length() - 1) {
//                    temp.add(new int[]{-1, -1});
//                }
//            }
//        }
//        int[][] ans = new int[temp.size()][2];
//        for (int i = 0; i < temp.size(); i++) {
//            ans[i][0] = temp.get(i)[0];
//            ans[i][1] = temp.get(i)[1];
//        }
//        return ans;
//    }

}
